#include "twenty_five.h"
#include <stdio.h>
#include <stdlib.h>

void extend_shortest_paths(int n, int **L, int **W, int **G)
{
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d -> %d(%d) *** ", i+1, j+1, L[i][j]);
            for (int k = 0; k < n; k++) {
                if(!(L[i][k] == __INT_MAX__ || W[k][j] == __INT_MAX__)) {
                    int w = L[i][k] + W[k][j];
                    if (L[i][j] > w) {
                        printf("%d -> %d(%d) -> %d(%d) *** ", i+1, k+1, L[i][k], j+1, w);
                        L[i][j] = w;
                        G[i][j] = k;
                    }
                }
            }
            printf("Over\n");
        }
    }
    print_mat(n, L);
}

void slow_all_pairs_shortest_paths(int n, int **L, int **W, int **G)
{
    printf("L(1)\n");
    print_mat(n, L);
    for (int m = 2; m <= n-1; m++) {
        printf("L(%d)\n", m);
        extend_shortest_paths(n, L, W, G);
    }
}

void print_mat(int n, int **L) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if(L[i][j] == __INT_MAX__) printf(" Inf");
            else printf("%4d", L[i][j]);
        }
        printf("\n");
    }
    printf("--------------------\n");
}

void print_pairs_shortest_path(int **G, int i, int j)
{
    if (i == j) {
        printf("%d\n", i+1);
    } else if (G[i][j] == __INT_MAX__) {
        printf("no path from %d --> %d\n", i+1, j+1);
    } else {
        printf("%d <-- ", j+1);
        print_pairs_shortest_path(G, i, G[i][j]);

    }
}

void print_all_pairs_shortest_path(int **G, int n)
{
    for(int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if(i == j) {
                continue;
            }
            printf("**** %d --> %d ****\n", i+1, j+1);
            print_pairs_shortest_path(G, i, j);
        }
    }
}

void faster_all_paris_shortest_paths(int n, int **W, int **G)
{
    int m = 1;
    while (m < n-1) {
        extend_shortest_paths(n, W, W, G);
        m = 2*m;
    }
}

void floyd_marshall(int n, int **D, int **G)
{
    for(int k = 0; k < n; k++) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
//                printf("%d -> %d(%d) *** ", i+1, j+1, D[i][j]);
                if(!(D[i][k] == __INT_MAX__ || D[k][j] == __INT_MAX__)) {
                    int w = D[i][k] + D[k][j];
                    if (D[i][j] > w) {
//                        printf("%d -> %d(%d) -> %d(%d) *** ", i+1, k+1, D[i][k], j+1, w);
                        D[i][j] = w;
                        G[i][j] = G[k][j];
                    } else {
                        G[i][j] = G[i][j];
                    }
                }
//                printf(" Over\n");
            }
        }
        printf("D(%d)\n", k+1);
        print_mat(n, D);
        printf("II(%d)\n", k+1);
        print_mat(n, G);
    }
}

void transitive_closure(int n, int **W, int **T)
{
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if((i == j) || (W[i][j] != __INT_MAX__)) {
                T[i][j] = 1;
            } else {
                T[i][j] = 0;
            }
        }
    }
    for(int k = 0; k < n; k++) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                T[i][j] = T[i][j] | (T[i][k] & T[k][j]);
            }
        }
    }
}

void johnson(struct TF_List *list, int **D, int **G)
{
    struct TF_Node * node = (struct TF_Node *)malloc(sizeof(struct TF_Node));
    node->v = (struct TF_Item){
            0,
            __INT_MAX__,
            0,
            0,
            0,
            White,
            nullptr,
            nullptr,
            nullptr,
            __INT_MAX__,
    };
    node->pre = nullptr;
    struct TF_Adjacency_List ad_list = {nullptr, nullptr, 0};
    struct TF_Node * current = list->head;
    while(current != nullptr) {
        TF_adjacency_list_insert(&ad_list, current, 0);
        current = current->next;
    }
    node->v.list = &ad_list;
    node->next = list->head;
    list->head = node;
    list->count++;

    TF_list_show(list);

    int is_cycle = bellman_ford(list, node);
    if(is_cycle == 0) {
        printf("the input graph contains a negative-weight cycle");
    } else {
        TF_Node * u = list->head;
        while(u != nullptr) {
            TF_Adjacency_Node * v = u->v.list->head;
            while(v != nullptr) {
                v->v.w = v->v.w + u->v.d - v->v.v->v.d;
                v = v->next;
            }
            u->v.h = u->v.d;
            u = u->next;
        }
        TF_adjacency_list_clear(&ad_list);
        list->head = node->next;
        list->head->pre = nullptr;
        list->count--;
        int node_i = 0;
        free(node);
        u = list->head;
        while(node_i < list->count) {
            current = list->head;
            while(current!=nullptr) {
                current->v.d = __INT_MAX__;
                current->v.pi = nullptr;
                current = current->next;
            }

            dijkstra(list);

            current = list->head;
            int col_j = 0;
            while(current!=nullptr) {
                D[node_i][col_j] = current->v.d + u->v.h - current->v.h;
                if (current->v.pi == nullptr) {
                    G[u->v.v-1][current->v.v-1] = current->v.v - 1;
                } else {
                    G[u->v.v-1][current->v.v-1] = current->v.pi->v.v - 1;
                }
                col_j++;
                current = current->next;
            }
            list->head = u->next;
            u->next->pre = nullptr;
            u->pre = list->tail;
            list->tail->next = u;
            u->next = nullptr;
            list->tail = u;

            u = list->head;
            node_i++;
            printf("Node: %d\n", node_i);
            TF_list_show(list);
        }
    }
}
